Internet Info 1994 March

home *** CD-ROM | disk | FTP | other *** search

/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / internet-drafts / draft-shenker-realtime-model-00.txt < prev next >

Wrap

Text File | 1993-10-26 | 112.7 KB | 2,296 lines

Internet Draft Scott Shenker Expires: April 1994 Xerox PARC File: draft-shenker-realtime-model-00.txt David D. Clark MIT Lixia Zhang Xerox PARC A Service Model for an Integrated Services Internet October 22, 1993 Status of Memo This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its Areas, and its Working Groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months. Internet-Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet- Drafts as reference material or to cite them other than as a "working draft" or "work in progress." Abstract The Internet is currently being confronted with service demands from a new generation of applications. Supporting these applications effectively and efficiently will require extending the current Internet "best-effort" service model to one that offers an integrated suite of services. The purpose of this memo (which is derived primarily from [1]) is to describe a proposed "core" service model for an integrated services Internet. In the Appendix we discuss the process by which such a service model could be standardized by the IETF. 1 Introduction The current Internet offers a very simple service model: all packets receive the same "best effort" service. The term "best effort" means that the network tries to forward packets as soon as possible, but makes no quantitative commitments about the quality of service delivered. This service model can be realized by using a single FIFO queue to do packet scheduling in the switches; in fact, this service model arose precisely because FIFO packet scheduling, without admission control, cannot efficiently deliver any other service model. This single class "best effort" service model provides the Shenker, Clark, Zhang [Page 1] Internet Draft Integrated Service Architecture October 1993 same quality of service to all flows [Note 1] ; this uniform quality of service is good, as measured by delay and dropped packets, when the network is lightly loaded but can be quite poor when the network is heavily utilized. Consequently, only those applications that are rather tolerant of this variable service, such as file transfer (e.g., FTP), electronic mail, and interactive terminals (e.g., Telnet) have become widely adopted in the Internet. However, we expect there to soon be widespread demand for an emerging generation of computer based applications, such as FAX, remote video, multimedia conferencing, data fusion, remote X-terminals, visualization, and virtual reality. These applications represent a wide variety of quality of service requirements, ranging from the asynchronous nature of FAX and electronic mail to the extremely time-sensitive nature of high quality audio, and from the low bandwidth requirements of Telnet to the bandwidth intensive requirements of HDTV. To meet all of these service requirements using the current Internet service model, it would be necessary (but perhaps not sufficient) to keep the utilization level extremely low. We think a better solution is to offer a more sophisticated service model, so that applications can specify their service needs and the network can then allocate its resources selectively towards those applications that are more performance sensitive. It is important to emphasize that this solution requires that applications explicitly specify their service desires; these needs are not derived implicitly by the network through the inspection of port numbers. The service model is the enduring, and therefore the most fundamental, part of a network architecture. The service model will be incorporated into the network service interface used by future applications; as such, it will define the set of services they can request, and will therefore influence the design of future applications as well as the performance of existing ones. Thus, the service model should not be designed in reference to any specific network artifact but rather should be based on fundamental service requirements. While both the underlying network technology and the overlying suite of applications will evolve, the need for compatibility requires that this service interface remain relatively stable. Actually, compatibility only demands that the existing parts of the service model must remain largely unchanged; the service model should be extensible with augmentations handled without difficulty. Also, we should note that these compatibility arguments apply "only" _________________________ [Note 1] "Flow" is the term we use to refer to end-to-end connections and other more general varieties of traffic streams. We will return to this issue in Section 2 where we discuss multicast flows more explicit- ly. Shenker, Clark, Zhang [Page 2] Internet Draft Integrated Service Architecture October 1993 to those aspects of the service model which are part of the network service interface; the service model will also have some components (e.g., the link-sharing services as defined in Section 3) which are exercised through a network management interface, and here the compatibility arguments do not apply with nearly the same force. This memo proposes a core service model for the Internet. We address those services which relate most directly to the time-of-delivery of packets. We do not address those services which are concerned with which network links are used (which is the domain of routing) and those services which involve encryption, security, authentication, or transmission reliability. We also do not consider services, such as reliable multicast, which do tangentially involve the time-of- delivery but which more fundamentally involve other factors such as buffer management and inter-switch acknowledgment algorithms. Furthermore, we do not consider time-of-delivery services which can best be delivered at the end host or by gateway switches at the edge of the network, such as synchronization of different traffic streams. Although many of the services listed above may perhaps be offered in the future, we do not expect that they will affect the basic core of the service model which we discuss here. In order to efficiently support this more sophisticated service model, Internet routers must employ an appropriately sophisticated non-FIFO packet scheduling algorithm. In fact, the packet scheduling algorithm is the most fundamental way in which the network can allocate resources selectively; the network can also allocate selectively via routing or buffer management algorithms, but neither of these by themselves can support a sufficiently general service model (see [10,6,7,15,9,11,13,29,18,19] for a few examples of packet scheduling algorithms). However, packet scheduling algorithms are only part of a complete mechanism to support explicit qualities of service. In particular, since resources are finite, one cannot always support an unbounded number of service requests. The network must employ some form of admission algorithm so that it has control over which service commitments are made. The admission process requires that flows characterize their traffic stream to the network when requesting service, and the network then determines whether or not to grant the service request. It is important to keep in mind that admission control plays a crucial role in allowing these scheduling algorithms to be effective by keeping the aggregate traffic load down to a level where meeting the service commitments is feasible (see [7,20,22,24] for a few examples of admission control algorithms). In fact, admission control is but one kind of denial of service; we will discuss the several varieties of denial of service and their role in allowing the scheduling algorithm to meet service commitments. This memo has 2 sections. In Section 30 we identify the two kinds of Shenker, Clark, Zhang [Page 3] Internet Draft Integrated Service Architecture October 1993 service commitments we expect future networks to make; these are quality of service commitments to individual flows and resource- sharing commitments to collective entities. In Section 31 we explore the service requirements of individual flows and then propose a corresponding set of service models. In Section 3 we discuss the service requirements for resource-sharing commitments to collective entities, and propose a related service model. In Section 32, we review the various forms denial of service can manifest, and the ways in which denial of service can be used to augment the core service model. We then conclude in Section 2 by discussing other viewpoints. In an Appendix we discuss how the Internet community can standardize a new service model. 2 Service Commitments A service model is made up of service commitments; that is, a service model describes what service the network commits to deliver in response to a particular service request. In this section, we describe the various different kinds of service commitments that are included in our core service model. Service commitments can be divided up into two classes, depending on the way in which the service is characterized. One class of service commitment is a quantitative or absolute service commitment, which is some form of assurance that the network service will meet or exceed the agreed upon quantitative specifications; a typical example of this is a bound on maximal packet delay. The other class of service commitment is a qualitative or relative service commitment, which is merely some form of assurance about how one set of packets will be treated relative to other sets of packets. One example of this kind of relative service commitment is to offer several different priority classes; the service in any priority class is not quantitatively characterized, but there is a relative commitment to serve traffic in a given priority class before traffic in lower priority classes. Thus, when we say that the current Internet offers only a single "best-effort" class of service, this is equivalent to saying that it does not offer any quantitative service commitments, and only offers the most trivial relative service commitment to treat all packets equivalently. An important distinction between these two classes of commitments is that quantitative service commitments often inherently require some form of admission control, with the flow characterizing its traffic in some manner; in contrast, relative service commitments generally do not require any admission control. Service commitments can also be divided into two categories depending on the entities to which the commitments are made. The first category of service commitments is the one most often considered in the current literature; these are quality of service commitments to Shenker, Clark, Zhang [Page 4] Internet Draft Integrated Service Architecture October 1993 individual flows. In this case the network provides some form of assurance that the quality of service delivered to the contracting flow will meet or exceed the agreed upon specifications. The need for these kinds of service commitments is usually driven by the ergonomic requirements of individual applications. For instance, the perceived quality of many interactive audio and video applications declines dramatically when the delay of incoming packets becomes too large; thus, these applications would perform better if the network would commit to a small bound on the maximum packet queueing delay. In Section 3 we discuss what quality of service commitments are included in our core service model. In contrast, the second category of service commitment we consider has rarely been explicitly discussed in the research literature, even though there is widespread agreement in the industry that there is great customer demand for this feature; these are resource-sharing commitments to collective entities. In this case, the network provides an assurance that the resource in question will be shared according to some prearranged convention among some set of collective entities. These collective entities could, for example, be institutions, protocol families, or application types. An example of the need for such resource-sharing commitments is when two private companies choose to jointly purchase a fiber optic link and then elect to share the bandwidth in proportion to the capital investments of the two companies. In Section 4, we present a more detailed motivation for this form of service commitment and then discuss the particular resource-sharing commitments that are part of our core service model. We should reiterate that because the quality of service service commitments to individual flows will typically be invoked through the service interface, compatibility requires that their definition remain relatively stable. The resource sharing commitments will typically be invoked through a network management interface, not through the service interface used by applications, and therefore the need for compatibility does not require such a stable service definition. 3 Quality of Service Requirements and Service Models In the previous section, we distinguished two sorts of service requirements, quality of service requirements and resource sharing requirements. In this section we consider quality of service requirements. We first argue that packet delay is the key measure of quality of service. We then present our assumptions about the nature of future computer-based applications and their service requirements. Finally, we describe a set of quality of service commitments designed to meet these service requirements. Shenker, Clark, Zhang [Page 5] Internet Draft Integrated Service Architecture October 1993 3.1 The Centrality of Delay There is one measure of service that is relevant to almost all applications: per-packet delay. In some sense, delay is the fundamental measure of the service given to a packet, since it describes when (and if) a packet is delivered and, if we assume that data is never corrupted (which we think is a good approximation for the future Internet [Note 2] ), the time of delivery is the only quantity of interest to applications. Delay is clearly the most central quality of service, and we will therefore start by assuming that the only qualities of service about which the network makes commitments relate to per-packet delay. Later, in Section 2 we will return to this point and ask if the service model that results from this initial assumption is sufficiently general. In addition to restricting our attention to delay, we make the even more restrictive assumption that the only quantity about which we make quantitative service commitments are bounds on the maximum and minimum delays. Thus, we have excluded quantitative service commitments about other delay related qualities of service, such as targets for average delay. This is based on three judgments. First, controlling nonextremal values of delay through packet scheduling algorithms is usually impractical because it requires detailed knowledge of the actual load, rather than just knowledge of the best and worst case loads. Second, even if one could control nonextremal measures of packet delay for the aggregate traffic in the network, this does not control the value of such measures for individual flows; e.g., the average delay observed by a particular flow need not be the same as, or even bounded by, the average of the aggregate (see [33] for a discussion of related issues). Thus, controlling nonextremal measures of delay for the aggregate is not sufficient, and we judge it impractical to control nonextremal measures of delay for each individual flow. Third, as will be argued in the next section, applications that require quantitative delay bounds are more sensitive to the extremes of delay than the averages or other statistical measures, so even if other delay related qualities of service were practical they would not be particularly useful. We discuss this in the section below when we discuss real-time applications. Why have we not included bandwidth as a quality of service about _________________________ [Note 2] For those links where this is not a good approximation, such as some wireless links, we expect there to be hop-by-hop error recovery so that at the network level there is a low error rate. Shenker, Clark, Zhang [Page 6] Internet Draft Integrated Service Architecture October 1993 which the network makes commitments? This is primarily because, for applications which care about the time-of-delivery of each packet, the description of per-packet delay is sufficient. The application determines its bandwidth needs, and these needs are part of the traffic characterization passed to the network's admission control algorithm; it is the application which then has to make a commitment about the bandwidth of its traffic (when requesting a quantitative service commitment from the network), and the network in turn makes a commitment about delay. However, there are some applications which are essentially indifferent to the time-of-delivery of individual packets; for example, when transferring a very long file the only relevant measure of performance is the finish time of the transfer, which is almost exclusively a function of the bandwidth. We discuss such applications at the end of Section 2. 3.2 Application Delay Requirements The degree to which application performance depends on low delay service varies widely, and we can make several qualitative distinctions between applications based on the degree of their dependence. One class of applications needs the data in each packet by a certain time and, if the data has not arrived by then, the data is essentially worthless; we call these real-time applications. Another class of applications will always wait for data to arrive; we call these elastic applications. We now consider the delay requirements of these two classes separately. For the purposes of the discussion that follows, we assume that all applications involve point-to-point communication, with all packets requiring the same service. At the end of Section 2 we discuss the case of multipoint-to-multipoint communication. In Section 32 we address the case where some packets in a flow are more important than others. 3.2.1 Real-Time Applications An important class of such real-time applications, which are the only real-time applications we explicitly consider in the arguments that follow, are "playback" applications. In a playback application, the source takes some signal, packetizes it, and then transmits the packets over the network. The network inevitably introduces some variation in the delay of the delivered packets. This variation in delay has traditionally been called "jitter". The receiver depacketizes the data and then attempts to faithfully play back the signal. This is done by buffering the incoming data to remove the network induced jitter and then replaying the signal at some Shenker, Clark, Zhang [Page 7] Internet Draft Integrated Service Architecture October 1993 fixed offset delay from the original departure time; the term "playback point" refers to the point in time which is offset from the original departure time by this fixed delay. Any data that arrives before its associated playback point can be used to reconstruct the signal; data arriving after the playback point is essentially useless in reconstructing the real-time signal [Note 3] purposes of discussion, let us temporarily assume that such playback applications have some intrinsic data generation process that is unalterable; later in this section we will return to this point. In order to choose a reasonable value for the offset delay, an application needs some "a priori" characterization of the maximum delay its packets will experience. This "a priori" characterization could either be provided by the network in a quantitative service commitment to a delay bound, or through the observation of the delays experienced by the previously arrived packets; the application needs to know what delays to expect, but this expectation need not be constant for the entire duration of the flow. The performance of a playback application is measured along two dimensions: latency and fidelity. In general, latency is the delay between the two (or more) ends of a distributed application; for playback applications, latency is the delay between the time the signal is generated at the source and the time the signal is played back at the receiver, which is exactly the offset delay. Applications vary greatly in their sensitivity to latency. Some playback applications, in particular those that involve interaction between the two ends of a connection such as a phone call, are rather sensitive to the value of the offset delay; other playback applications, such as transmitting a movie or lecture, are not. Fidelity is the measure of how faithful the playback signal is to the original signal. The playback signal is incomplete when packets arrive after their playback point and thus are dropped rather than played back. The playback signal becomes distorted when the offset delay is varied. Therefore, fidelity is decreased whenever the offset delay is varied and whenever packets miss their playback point. Applications exhibit a wide range of sensitivity to loss of fidelity. We will consider two somewhat artificially dichotomous classes: intolerant _________________________ [Note 3] It is an oversimplification to say that the data is useless; we discuss below that a receiving application could adjust the playback point as an alternative to discarding late packets. Shenker, Clark, Zhang [Page 8] Internet Draft Integrated Service Architecture October 1993 applications, which require an absolutely faithful playback, and tolerant applications, which can tolerate some loss of fidelity [Note 4]. Intolerance to loss of fidelity might arise because of user requirements (e.g., distributed symphony rehearsal), or because the application hardware or software is unable to cope with missing pieces of data. On the other hand, users of tolerant applications, as well as the application hardware and software, are prepared to accept occasional distortions in the signal. We expect that the vast bulk of audio and video applications will be tolerant. Delay can affect the performance of playback applications in two ways. First, the value of the offset delay, which is determined by predictions about the future packet delays, determines the latency of the application. Second, the delays of individual packets can decrease the fidelity of the playback by exceeding the offset delay; the application then can either change the offset delay in order to play back late packets (which introduces distortion) or merely discard late packets (which creates an incomplete signal). The two different ways of coping with late packets offer a choice between an incomplete signal and a distorted one, and the optimal choice will depend on the details of the application, but the important point is that late packets necessarily decrease fidelity. Intolerant applications must use a fixed offset delay, since any variation in the offset delay will introduce some distortion in the playback. For a given distribution of packet delays, this fixed offset delay must be larger than the absolute maximum delay, to avoid the possibility of late packets. In contrast, tolerant applications need not set their offset delay greater than the absolute maximum delay, since they can tolerate some late packets. Moreover, tolerant applications can vary the offset delay to some extent, as long as it doesn't create too much distortion. Thus, tolerant applications have a much greater degree of flexibility in how they set and adjust their offset delay. In particular, instead of using a single fixed value for the offset delay, they can attempt to reduce their latency by varying their offset delays in response to the actual packet _________________________ [Note 4] Obviously, applications lie on a continuum in their sensitivity to fidelity. Here we are merely considering two cases as a pedagogical device to motivate our service model, which indeed applies to the full spectrum of applications. Shenker, Clark, Zhang [Page 9] Internet Draft Integrated Service Architecture October 1993 delays experienced in the recent past. We call applications which vary their offset delays in this manner "adaptive" playback applications (a more precise term is "delay-adaptive" playback applications, to distinguish it from the "rate- adaptive" playback applications we discuss below). This adaptation amounts to gambling that the past packet delays are good predictors of future packet delays; when the application loses the gamble there is a momentary loss of data as packets miss their playback points, but since the application is tolerant of such losses the decreased offset delay may be worth it. Besides the issue of inducing late packets, there is a complicated tradeoff between the advantage of decreased offset delay and the disadvantage of reduced fidelity due to variations in the offset. Thus, how aggressively an application adapts, or even if it adapts at all, depends on the relative ergonomic impact of fidelity and latency. Our main observation here, though, is that by adapting to the delays of incoming packets, tolerant playback applications can often profit by reducing their offset delay when the typical delays are well below the absolute maximum; this advantage, of course, is accompanied by the risk of occasional late packets. So far we have assumed that an application's data generation process is unalterable. However, there are likely to be many audio and video applications which can adjust their coding scheme and thus can alter the resulting data generation process. This alteration of the coding scheme will present a tradeoff between fidelity (of the coding scheme itself, not of the playback process) and the bandwidth requirements of the flow. Such "rate-adaptive" playback applications have the advantage that they can adjust to the current network conditions not just by resetting their playback point but also by adjusting the traffic pattern itself. We now state several of our assumptions about the nature of future real-time applications. First, we believe that most audio and video applications will be playback applications, and we therefore think that playback applications will be the dominant category of real-time traffic. By designing a service model that is appropriate for these playback applications, we think we will have satisfactorily (but perhaps not optimally) met the needs of all real-time applications. Second, we believe that the vast majority of playback applications will be tolerant and that many, if not most, of these tolerant playback applications will be adaptive. The idea of adaptive applications is not relevant to circuit switched networks, which do not have jitter due to queueing. Thus, most real-time devices today, like voice and video codecs, are not adaptive. Shenker, Clark, Zhang [Page 10] Internet Draft Integrated Service Architecture October 1993 Lack of widespread experience may raise the concern that adaptive applications will be difficult to build. However, early experiments suggest that it is actually rather easy. Video can be made to adapt by dropping or replaying a frame as necessary, and voice can adapt imperceptibly by adjusting silent periods. In fact, such adaptive approaches have been employed in packetized voice applications since the early 70's (see [34,36]); the VT [37], NEVOT [38], and VAT [] packet voice protocols, which are currently used to transmit voice on the Internet, are living examples of such adaptive applications. Third, we believe that most playback applications will have sufficient buffering to store packets until their playback point. We base our belief on the fact that the storage needed is a function of the queueing delays, not the total end-to-end delay. There is no reason to expect that queueing delays for playback applications will increase as networks get faster (in fact, for an M/M/1 queueing system with a fixed utilization, queueing delays are inversely proportional to the speed), and it is certainly true that memory is getting cheaper, so providing sufficient buffering will become increasingly practical. Fourth, and last, we assume that applications have sufficient knowledge about time to set the playback point. The notion of a playback application implies that such applications have some knowledge about the original generation time of the data. This knowledge could either be explicitly contained in timestamps, or an approximation could be implicitly obtained by knowing the inter-packet generation intervals of the source. 3.2.2 Elastic Applications While real-time applications do not wait for late data to arrive, elastic applications will always wait for data to arrive. It is not that these applications are insensitive to delay; to the contrary, significantly increasing the delay of a packet will often harm the application's performance. Rather, the key point is that the application typically uses the arriving data immediately, rather than buffering it for some later time, and will always choose to wait for the incoming data rather than proceed without it. Because arriving data can be used immediately, these applications do not require any a priori characterization of the service in order for the application to function. Generally speaking, it is likely that for a given distribution of packet delays, the perceived performance of elastic applications will tend to depend more on the average delay than on the tail of the distribution. One can think of several categories of such elastic applications: interactive burst (Telnet, X, NFS), interactive bulk transfer Shenker, Clark, Zhang [Page 11] Internet Draft Integrated Service Architecture October 1993 (FTP), and asynchronous bulk transfer (electronic mail, FAX). The delay requirements of these elastic applications vary from rather demanding for interactive burst applications to rather lax for asynchronous bulk transfer, with interactive bulk transfer being intermediate between them. Some elastic applications, like Telnet, have an intrinsic data generation process which is largely independent of network conditions. However, there are many elastic applications, in particular those involving bulk transfer, which can alter their packet transmission process. 3.3 Delay Service Models We now turn to describing service models that are appropriate for the various classes of applications that were discussed in the previous paragraphs. Since we are assuming that playback applications comprise the bulk of the real-time traffic, we must design service models for intolerant playback applications, tolerant playback applications (which can be either adaptive or non-adaptive), rate-adaptive playback applications (which can be either tolerant or intolerant), and elastic applications. The offset delay of intolerant playback applications must be no smaller than the maximum packet delay to achieve the desired faithful playback. Furthermore, this offset delay must be set before any packet delays can be observed. Such an application can only set its offset delay appropriately if it is given a perfectly reliable [Note 5] upper bound on the maximum delay of each packet. We call a service characterized by a perfectly reliable upper bound on delay "guaranteed service", and propose this as the appropriate service model for intolerant playback applications. Note that the delay bound not only allows the application to set its offset delay appropriately, but it also provides the information necessary to predict the resulting latency of the application. Since such an intolerant playback application will queue all packets until their respective playback points, application performance is completely independent of when the packets arrive, as long as they arrive within the delay bound. The fact that we assume that there is sufficient buffering means that we need not _________________________ [Note 5] By perfectly reliable, we mean that the bound is based on worst case assumptions about the behavior of all other flows. The validity of the bound is predicated on the proper functioning of all network hardware and software along the path of the flow. Shenker, Clark, Zhang [Page 12] Internet Draft Integrated Service Architecture October 1993 provide a nontrivial lower bound to delay; only the trivial "no- queueing" minimum delay will be given as part of the service specification. A tolerant playback application which is not adaptive will also need some form of a delay bound so that it can set its offset delay appropriately. Since the application is tolerant of occasional late packets, this bound need not be perfectly reliable. For this class of applications we propose a service model called "predictive service" which supplies a fairly reliable, but not perfectly reliable, delay bound. For this service, the network advertises a bound which it has reason to believe with great confidence will be valid, but cannot formally "prove" its validity [Note 6] violated, the application's performance will perhaps suffer, but the users are willing to tolerate such interruptions in service in return for the presumed lower cost of the service and lower realized delays [Note 7] It is important to emphasize that this is "not" a statistical bound, in that no statistical failure rate is provided to the application in the service description. We do not think it feasible to provide a statistical characterization of the delay distribution because that would require a detailed statistical characterization of the load. We do envision the network ensuring the reliability of these predictive bounds, but only over very long time scales; for instance, the network could promise that no more than a certain fraction of packets would violate the predictive bounds over the course of a month [Note 8] is not a _________________________ [Note 6] This bound, in contrast to the bound in the guaranteed service, is not based on worst case assumptions on the behavior of other flows. Instead, this bound might be computed with properly conservative predic- tions about the behavior of other flows. [Note 7] For nonadaptive applications, the realized latency is lower with predictive service since the fairly reliable bounds will be less conservative than the perfectly reliable bounds of guaranteed service. For adaptive applications, as we discuss below, the minimax component of predictive service can, and we expect usually will, reduce the average latency, i.e. the average value of the offset delay, to be well below the advertised bound. [Note 8] Such an assurance is not meaningful to an individual flow, whose service over a short time interval might be significantly worse than the nominal failure rate. We envision that such assurances would be directed at the regulatory bodies which will supervise the adminis- tration of such networks. However, we should note that there may very well be pricing schemes which refund money if the service delivered to an individual application doesn't meet some standard (such as a given fraction of packets obey the delay bound); this is not a service commit- Shenker, Clark, Zhang [Page 13] Internet Draft Integrated Service Architecture October 1993 prediction of performance but rather a commitment to adjust its bound-setting algorithm to be sufficiently conservative. All nonadaptive applications, whether tolerant or not, need an "a priori" delay bound in order to set their offset delay; the degree of tolerance only determines how reliable this bound must be. In addition to being necessary to set the offset delay, these delay bounds provide useful estimates of the resulting latency. Nonadaptive tolerant applications, like the intolerant applications considered above, are indifferent to when their packets arrive, as long as they arrive before the delay bound. Recall, however, that we are assuming that many, if not most, tolerant playback applications are adaptive. Thus, we must design the service model with such adaptation in mind. Since these applications will be adapting to the actual packet delays, a delay bound is not needed to set the offset delay. However, in order to choose the appropriate level of service, applications need some way of estimating their performance with a given level of service. Ideally, such an estimate would depend on the detailed packet delay distribution. We consider it impractical to provide predictions or bounds on anything other than the extremal delay values. Thus, we propose offering the same predictive service to tolerant adaptive applications, except that here the delay bound is not primarily used to set the offset delay (although it may be used as a hint) but rather is used to predict the likely latency of the application. The actual performance of adaptive applications will depend on the tail of the delay distribution. We can augment the predictive service model to also give "minimax" service, which is to attempt to minimize the ex post maximum delay. This service is not trying to minimize the delay of every packet, but rather is trying to pull in the tail of the distribution. Here the fairly reliable predictive delay bound is the quantitative part of the service commitment, while the minimax part of the service commitment is a relative service commitment. We could offer separate service models for adaptive and nonadaptive tolerant playback applications, with both receiving the predictive service as a quantitative service commitment and with only adaptive applications receiving the minimax relative commitment. However, since the difference in the service models is rather minor, we choose to only offer the combination of predictive and minimax service. _________________________ ment but rather a monetary one. Shenker, Clark, Zhang [Page 14] Internet Draft Integrated Service Architecture October 1993 It is clear that given a choice, with all other things being equal, an application would perform no worse with absolutely reliable bounds than with fairly reliable bounds. Why, then, do we offer predictive service? The key consideration here is efficiency [Note 9] ; when one relaxes the service requirements from perfectly to fairly reliable bounds, this increases the level of network utilization that can be sustained, and thus the price of the predictive service will presumably be lower than that of guaranteed service. The predictive service class is motivated by the conjecture that the performance penalty will be small for tolerant applications but the overall efficiency gain will be quite large. As we discussed above, both of these service models have a quantitative component. In order to offer this service, the nature of the traffic from the source must be characterized, and there must be some admission control algorithm which insures that a requested flow can actually be accommodated. This characterization will not be a detailed statistical characterization (we do not believe applications will be able to provide those) but instead will be a worst-case characterization; the flow will commit to not exceed some usage envelope or filter (e.g., a token bucket or leaky bucket). A fundamental point of our overall architecture is that traffic characterization and admission control are necessary for these real-time delay bound services. For rate-adaptive applications, these traffic characterizations are not immutable. We can thus augment the service model by allowing the network to notify (either implicitly through packet drops or explicitly through control packets) rate- adaptive applications to change their traffic characterization. We will discuss this more thoroughly in Section 32. The fourth category for which we must develop a service model is elastic applications. Elastic applications are rather different than playback applications; while playback applications hold packets until their playback time, elastic applications use the packet whenever it arrives. Thus, reducing the delays of any packet tends to improve performance. Furthermore, since there is no offset delay, there is no need for an "a priori" characterization of the delays. An appropriate service model is to provide "as-soon-as-possible", or ASAP service, which is a relative, not quantitative, commitment [Note 10]. Elastic _________________________ [Note 9] Efficiency can be thought of as the number of applications that can be simultaneously serviced with a given amount of bandwidth; for a fuller definition, see [,]. [Note 10] We choose not to use the term "best-effort" for the ASAP ser- vice since that connotes the FIFO service discipline. Shenker, Clark, Zhang [Page 15] Internet Draft Integrated Service Architecture October 1993 applications vary greatly in their sensitivity to delay (which, as we mentioned earlier, is probably more a function of the average delay than of the maximum delay), and so the service model for elastic traffic should distinguish between the various levels of delay sensitivity. We therefore propose a multiclass ASAP service model to reflect the relative delay sensitivities of different elastic applications. This service model allows interactive burst applications to have lower delays than interactive bulk applications, which in turn would have lower delays than asynchronous bulk applications. In contrast to the real-time service models, this service model does not provide any quantitative service commitment, and thus applications cannot predict their likely performance and are also not subject to admission control. However, we think that rough predictions about performance, which are needed to select a service class, could be based on the ambient network conditions and historical experience. If the network load is unusually high, the delays will degrade and the users must be prepared to tolerate this, since there was no admission control to limit the total usage. However, there may be some cases where an application (or the user of the application) might want to know more precisely the performance of the application in advance. For instance, a Telnet user might want to ensure that the delays won't interfere with her typing. For these cases, the application can request predictive service (since the firmness of the guaranteed bound is probably not required) provided it is willing to specify the maximum transmission rate desired. Note that since the network will then require compliance with the advertised transmission rate, the application cannot get a higher throughput rate than what it requested. There are two issues regarding the elastic service model [Note 11] that we do not address in this memo, and propose that these issues be revisited once the rest of the core service model is defined. First, there is the issue of relative treatment of flows. One could treat each elastic packet independently, and allocate service based merely on time-of-arrival and the level of ASAP service requested. Alternatively, one could also attempt to control the aggregate resources used by each individual flow, such as is done in the Fair Queueing service model as described in []. We do not address the relative treatment of various flows at this time, since it will not affect the basic service interface. _________________________ [Note 11] We have used the convenient, but perhaps confusing convention, of referring to elastic service and real-time service when in fact the terms real-time and elastic refer to a class of applications. Shenker, Clark, Zhang [Page 16] Internet Draft Integrated Service Architecture October 1993 Second, there is the issue of feedback. As we noted before, some elastic applications can adjust their transmis pattern. This adjustment can be in response to implicit signals, such a packet drops or delay, or explicit signals such as congestion bits in the packet header or separate control packets. Again, we do not address at this time the form or content of such feedback signals since they do not affect the basic service interface. At the beginning of this section, we made the initial assumption that delay was the only quality of service about which the network needed to make commitments. We now revisit this issue and ask if that is indeed the case. For the typical real-time or elastic application which cares about the delays of individual packets, there seems to be no need to include any other quality of service. However, we observed earlier that there are some applications, such as transfers of very long files, which are essentially indifferent to the delays of individual packets and are only concerned with overall delay of the transfer. For these "indifferent" applications, bandwidth rather than delay is a more natural characterization of the desired service, since bandwidth dictates the application performance. If such an application has no intrinsic overall delay requirement, then the desired service is to finish the transfer as quickly as possible. The desired service is "as-much-bandwidth-as-possible". By servicing packets as soon as possible, the ASAP service described above delivers exactly this as-much-bandwidth-as-possible service. Thus, while we did not explicitly consider bulk transfer applications, our proposed service model already provides the desired service for bulk transfer applications with no intrinsic overall delay requirements. However, if this bulk transfer application had some intrinsic overall delay requirement, i.e. it required the transfer to be completed within a certain time, then the ASAP service is no longer sufficient. Now, the appropriate service is to allow the application to request a specified amount of bandwidth; the application chooses this bandwidth amount so that the transfer will be completed in time. An application can secure a given amount of bandwidth through either of the real-time services. The per-packet delay bounds provided by these real-time services are superfluous to bulk transfer applications with overall delay requirements. While one could imagine a different service which provided a commitment on bandwidth but not per-packet delay, the difference between requesting a large delay bound and no delay bound is rather insignificant, and thus we expect that such indifferent applications with delay requirements will be adequately served by predictive service with very large delay bounds. This has the disadvantage that indifferent applications Shenker, Clark, Zhang [Page 17] Internet Draft Integrated Service Architecture October 1993 with delay requirements do not get as-much-bandwidth-as-possible, but are constrained to their reserved amount. Applications / \ / \ / \ Elastic Real-Time / | \ / | \ / \ / | \ / \ / | \ / \ Interactive Interactive Asynchronous Tolerant Intolerant Burst Bulk Bulk | | | | | | | | | | | | V V V V V _________ _________ _________ __________ __________ | ASAP | | ASAP | | ASAP | |Predictive| |Guaranteed| | Level 1 | | Level 2 | | Level 3 | | Minimax | | | |_________| |_________| |_________| |__________| |__________| Figure 1: Our rough taxonomy of applications and their associated service models. We have arbitrarily depicted three levels of ASAP service. Figure depicts our taxonomy of applications and the associated service models. This taxonomy is neither exact nor complete, but was only used to guide the development of the core service model. The resulting core service model should be judged not on the validity of the underlying taxonomy but rather on its ability to adequately meet the needs of the entire spectrum of applications. In particular, not all real-time applications are playback applications; for example, one might imagine a visualization application which merely displayed the image encoded in each packet whenever it arrived. However, non-playback applications can still use either the guaranteed or predictive real-time service model, although these services are not specifically tailored to their needs. Similarly, playback applications cannot be neatly classified as either tolerant or intolerant, but rather fall along a continuum; offering both guaranteed and predictive service allows applications to make their own tradeoff between cost, fidelity, and latency. Despite these obvious deficiencies in the taxonomy, we expect that it describes the service requirements of current and future applications well enough so Shenker, Clark, Zhang [Page 18] Internet Draft Integrated Service Architecture October 1993 that our core service model can adequately meet all application needs. We have defined the core service model in terms of point-to-point flows. We can easily generalize this service model to incorporate multipoint-to-multipoint flows. Clearly for elastic traffic there is no change to the service model. For the real-time service models, the delay bounds are specified for each point-to-point pair, and the traffic characterizations apply to the sum of the flow's traffic at each hop along the flow's path. 4 Resource-Sharing Requirements and Service Models The last section considered quality of service commitments; these commitments dictate how the network must allocate its resources among the individual flows. This allocation of resources is typically negotiated on a flow-by-flow basis as each flow requests admission to the network, and does not address any of the policy issues that arise when one looks at collections of flows. To address these collective policy issues, we now discuss resource-sharing service commitments. Recall that for individual quality of service commitments we focused on delay as the only quantity of interest. Here, we postulate that the quantity of primary interest in resource-sharing is aggregate bandwidth on individual links. Our reasoning for this is as follows. Meeting individual application service needs is the task of quality of service commitments; however, both the number of quantitative service commitments that can be simultaneously made, and the quantitative performance delivered by the relative service commitments, depend on the aggregate bandwidth. Thus, when considering collective entities we claim that we need only control the aggregate bandwidth available to the constituent applications; we can deal with all other performance issues through quality of service commitments to individual flows. Embedded within this reasoning is the assumption that bandwidth is the only scarce commodity; if buffering in the switches is scarce then we must deal with buffer- sharing explicitly, but we contend that switches should be built with enough buffering so that buffer contention is not the primary bottleneck. Thus, this component of the service model, called "link-sharing", addresses the question of how to share the aggregate bandwidth of a link among various collective entities according to some set of specified shares. There are several examples that are commonly used to explain the requirement of link-sharing among collective entities. Multi-entity link-sharing. -- A link may be purchased and used jointly by several organizations, government agencies or the like. They may wish to insure that under overload the link is shared in a Shenker, Clark, Zhang [Page 19] Internet Draft Integrated Service Architecture October 1993 controlled way, perhaps in proportion to the capital investment of each entity. At the same time, they might wish that when the link is underloaded, any one of the entities could utilize all the idle bandwidth. Multi-protocol link-sharing -- In a multi-protocol Internet, it may be desired to prevent one protocol family (DECnet, IP, IPX, OSI, SNA, etc.) from overloading the link and excluding the other families. This is important because different families may have different methods of detecting and responding to congestion, and some methods may be more "aggressive" than others. This could lead to a situation in which one protocol backs off more rapidly than another under congestion, and ends up getting no bandwidth. Explicit control in the router may be required to correct this. Again, one might expect that this control should apply only under overload, while permitting an idle link to be used in any proportion. Multi-service sharing -- Within a protocol family such as IP, an administrator might wish to limit the fraction of bandwidth allocated to various service classes. For example, an administrator might wish to limit the amount of real-time traffic to some fraction of the link, to avoid preempting elastic traffic such as FTP. In general terms, the link-sharing service model is to share the aggregate bandwidth according to some specified shares; however, one must be careful to state exactly what this means. The following example will highlight some of the policy issues implicit in link- sharing. Consider three firms, 1, 2, and 3, who respectively have shares 1/4, 1/4, and 1/2 of some link. Assume that for a certain hour, firm 1 sends no traffic to the link while firms 2 and 3 each send enough to use the entire capacity of the link. Are firms 2 and 3 restricted to only using their original shares of the link, or can they use firm 1's unused bandwidth? Assume for now that they are allowed to use firm 1's unused bandwidth. Then, how is firm 1's share of the link split between firms 2 and 3? If, in the next twenty minutes, all three firms each send enough traffic to consume the entire link, is the link allocated solely to firm 1 in order to make up for the imbalance in aggregate bandwidth incurred during the first hour, or is the link shared according to the original shares? Thus, there are three policy questions to be resolved: can firms use each other's unused bandwidth, how is this unused bandwidth allocated to the remaining firms, and over what time scale is the sharing of bandwidth measured? Clearly the answer to the first question must be affirmative, since much of the original motivation for link-sharing is to take advantage of the economies of statistical aggregation. As for the second question, one can imagine many rules for splitting up the excess bandwidth but here we propose that the excess is assigned in proportion to the original shares so that in the above example Shenker, Clark, Zhang [Page 20] Internet Draft Integrated Service Architecture October 1993 during the first hour the link would be split 1/3, 2/3 for firms 2 and 3 respectively. The answer to the third question is less clear. The preceding example indicates that if sharing is measured over some time scale T then a firm's traffic can be halted for a time on the order of T under certain conditions; since such cessation should be avoided, we propose doing the sharing on an instantaneous basis (i.e., the limit of T going to zero). This would dictate that during this next twenty minutes the bandwidth is split exactly according to the original shares: 1/4, 1/4, and 1/2. This policy embodies a "use-it-or-lose-it" philosophy in that the firms are not given credit at a later date for currently unused bandwidth. An idealized fluid model of instantaneous link-sharing with proportional sharing of excess is the fluid processor sharing model (introduced in [] and further explored in [29,18]) where at every instant the available bandwidth is shared between the active entities (i.e., those having packets in the queue) in proportion to the assigned shares of the resource. More specifically, we let mu be the speed of the link and we give each entity i its own virtual queue which stores its packets as they await service. For each entity i we define the following quantities: s_i, the share of the link; c_i(t), the cumulative number of bits in the traffic stream that have arrived by time t; and the backlog b_i(t), the number of bits remaining in the virtual queue at time t. Whenever a real packet arrives at the switch belonging to entity i, we place a corresponding idealized packet at the tail of that entity's virtual queue. The service within each such virtual queue is FIFO. We now describe how service is allocated among the different virtual queues. The idealized service model is defined by the equations: b_i'(t) = c_i' - min( S_i*L, c_i' ) if b_i(t) = 0 (1) and b_i'(t) = c_i' - s_i*L if b_i(t) > 0 (2) where prime represents differentiation with respect to time and L is the unique constant that makes: (Sum over i of b_i' ) = Mu - ( Sum over i of c_i' ); when no such value exists, we set L to infinity. At every instant the excess bandwidth, that is the bandwidth left over from flows not using their entire share of bandwidth, is split among the active entities (i.e., those with bi>0) in proportion to their shares; each active [Note 12] entity receives an instantaneous _________________________ Shenker, Clark, Zhang [Page 21] Internet Draft Integrated Service Architecture October 1993 bandwidth that is greater than or equal to their share of the full transmission rate. This fluid model exhibits the desired policy behavior but is, of course, an unrealistic idealization. We then propose that the actual service model should be to approximate, as closely as possible, the bandwidth shares produced by this ideal fluid model. It is not necessary to require that the specific order of packet departures match those of the fluid model since we presume that all detailed per-packet delay requirements of individual flows are addressed through quality of service commitments and, furthermore, the satisfaction with the link-sharing service delivered will probably not depend very sensitively on small deviations from the scheduling implied by the fluid link-sharing model. The link-sharing service model provides quantitative service commitments on bandwidth shares that the various entities receive. Heretofore we have considered link-sharing across a set of entities with no internal structure to the entities themselves. However, the various sorts of link-sharing requirements presented above could conceivably be nested into a hierarchy of link-sharing requirements, an idea first proposed by Jacobson and Floyd [11]. For instance, a link could be divided between a number of organizations, each of which would divide the resulting allocation among a number of protocols, each of which would be divided among a number of services. We propose extending the idealized link-sharing service model presented above to the hierarchical case. The policy desires will be represented by a tree with shares assigned to each node; the shares belonging to the children of each node must sum to the share of the node, and the top node represents the full link and has a unit share. Furthermore, each node has an arrival stream described by ci(t) and a backlog b_i(t) with the quantities of the children of each node summing to the quantity of the node. Then, at each node we invoke the fluid processor sharing model among the children, with the instantaneous link speed at the i'th node, mu_i(t), set equal to the rate b_i'(t) at which bits are draining out of that node's virtual queue. We can start this model at the top node; when propagated down to the leaf nodes, or bottom-level entities, this determines the idealized service model. The introduction of a hierarchy raises further policy questions which are illustrated by the following example depicted in Figure `a' and `b'. Let us assume that each of the bottom-level entities, 1a, 1b, 2a and 2b, has a 1/4 share of the link. When all of the bottom-level _________________________ [Note 12] There are three states a flow can be in: active (b_i>0), inac- tive (b_i=0 and c_i'=0), and in-limbo (b_i=0 but c_i'>0). Shenker, Clark, Zhang [Page 22] Internet Draft Integrated Service Architecture October 1993 entities are sending enough to consume their share, the bandwidth is split exactly according to these shares. Now assume that at some instant there is no offered 2b traffic. Should each of 1a,1b and 2a get 1/3 of the link, or should 1a and 1b continue to get 1/4, with 2a getting the remaining 1/2 share of the link which is the total of the shares belonging to firm 2? This is a policy question to be determined by the firms, so the service model should allow either. Figure depicts two possible sharing trees. Tree #1 in the figure produces the 1/4, 1/4, 1/2 sharing whereas tree #2 produces the 1/3, 1/3, 1/3 sharing. When the link-sharing service commitment is negotiated, it will be specified by a tree and an assignment of shares for the nodes. Link / \ Link / \ / \ / / \ \ 1 2 / / \ \ / \ / \ / | | \ / \ / \ / | | \ 1a 1b 2a 2b 1a 1b 2a 2b Tree #1 Tree #2 Figure 2: Two possible sharing trees with equal shares at all leaf nodes. When one of the leaf nodes is not active, the trees produce different bandwidth shares for the remaining active nodes. In the hierarchical model, the bandwidth sharing between the children of a given node was independent of the structure of the grandchildren. One can think of far more general link-sharing service models. Assume that in the example above that protocol `a' carries traffic from applications with tight delay requirements and protocol `b' carries traffic from applications with loose delay requirements. The two firms might then want to implement a sharing policy that when 1a is not fully using its share of the link, the excess is shared equally among 1b and 2a, but when 1b is not fully using its share of the link we will give the excess exclusively to 1a. To implement this more complicated policy, it is necessary to take the grandchildren structure into account. We think that this sort of flexibility is probably not needed, for the same reason that we restricted ourselves to bandwidth as the only collective concern; quality of service issues should be addressed via quality of service commitments and not through the link-sharing service model. For this same reason, we do not make priority distinctions between the various Shenker, Clark, Zhang [Page 23] Internet Draft Integrated Service Architecture October 1993 nodes, but merely allocate shares of bandwidth. Therefore, for our resource-sharing service model we restrict ourselves to the hierarchical service model presented above. In Section 31 we observed that admission control was necessary to ensure that the real-time service commitments could be met. Similarly, admission control will again be necessary to ensure that the link-sharing commitments can be met. For each bottom-level entity, admission control must keep the cumulative guaranteed and predictive traffic from exceeding the assigned link-share. 5 Denial of Service To meet its quantitative service commitments, the network must employ some form of admission control. Without the ability to deny flows admission to the network, one could not reliably provide the various delay bound services offered by our service model. In fact, admission control is just one aspect of denial of service; there are several other ways in which service can be denied. Denial of service, in all of its incarnations, plays a fundamental role in meeting quantitative service commitments. In particular, denial of service can be used to augment the resource sharing portion of the core service model by supporting utilization targets. Moreover, denial of service, through the use of the preemptable and expendable service options discussed below, can enable the network to meet its service commitments while still maintaining reasonably high levels of network utilization. Denial of service, like service commitments, can occur at various levels of granularity. Specifically, denial of service can apply to whole flows, or to individual packets within a flow. We discuss these two cases separately. 5.1 Denial to Flows Denial of service to a flow can occur either before or during the lifetime of that flow. Denying service to a flow before it enters the network is typically referred to as admission control. As we envision it, in order to receive either of the two real-time bounded delay services (guaranteed and predictive), a flow will have to explicitly request that service from the network, and this request must be accompanied by a worst-case characterization of the flow's traffic stream. This characterization gives the network the information necessary to determine if it can indeed commit to providing the requested delay bounds. The request is denied if the network determines that it cannot reliably provide the requested service. References [7,20,22,24] discuss various approaches to admission control. Shenker, Clark, Zhang [Page 24] Internet Draft Integrated Service Architecture October 1993 In addition, a service model could offer a "preemptable" flow service, presumably for a lower cost than non-preemptable service. When the network was in danger of not meeting some of its quantitative service commitments, or even if the network was merely having to deny admission to other flows, then it could exercise the "preemptability option" on certain flows and immediately discontinue service to those flows by discarding their packets (and, presumably, sending a control message informing those flows of their termination). By terminating service to these preemptable flows, the service to the flows that are continuing to receive service will improve, and other non- preemptable flows can be admitted. Recall that rate-adaptive flows are able to adjust their transmission rate. For these flows we can offer an "adjustable" flow service, again presumably for a lower cost than the regular non-preemptable, non-adjustable service. When the network was in danger of not meeting some of its quantitative service commitments, or even if the network was merely having to deny admission to other flows, then it could exercise the "adjustability option" of these flows and request that they reduce their transmission rate. Similarly, when the network had spare capacity, it could inform these flows that they could increase their transmission rate. Admission control can be used to augment the link-sharing service model described in the previous section. Link-sharing uses packet scheduling to provide quantitative service commitments about bandwidth shares. This service is designed to provide sharing between various entities which have explicitly contracted with the network to manage that sharing. However, there are other collective policy issues that do not involve institutional entities, but rather concern overall utilization levels of the various service classes (guaranteed, predictive, ASAP). Because they are not explicitly negotiated, and so no service commitments are at stake, these utilization levels are not controlled by packet scheduling but instead are controlled by the admission control algorithm. All real-time flows are subject to scrutiny by the admission control process; only those flows that are accepted can use the network. If the admission control algorithm used the criteria that a flow was accepted if and only if it could be accepted without violating other quality of service commitments, then the utilization levels of the various classes will depend crucially on the order in which the service requests arrived to the network. One might desire, instead, to make explicit policy choices about these various level of utilization. For instance, it is probably advisable to prevent starvation of any particular class of traffic; an explicit control would be needed to prevent Shenker, Clark, Zhang [Page 25] Internet Draft Integrated Service Architecture October 1993 starvation of elastic traffic since the ASAP service does not involve resource reservation. In addition, one might want the admissions process to ensure that requests for large amounts of bandwidth were not always squeezed out by numerous smaller requests. To prevent such problems, we must introduce some guidelines, called "utilization targets", into the admission control algorithm so that the utilization levels are not just dependent on the details of the load pattern but instead are guided towards some preferred usage pattern. This utilization target service model involves only admission control; thus, it is not properly part of the core service model. We mention utilization targets here because other aspects of the core service model rely on these utilization targets, and also because it is so similar to the link-sharing model, in that it represents policy objectives for aggregated classes of traffic. 5.2 Denial To Packets While denial of service is usually associated with admission control, it also can be performed on a packet-by-packet granularity. Denial of service to individual packets could occur by means of a "preemptable" packet service, whereby flows would have the option of marking some of their packets as preemptable. When the network was in danger of not meeting some of its quantitative service commitments, it could exercise a certain packet's "preemptability option" and discard the packet (not merely delay it, since that would introduce out-of-order problems). By discarding these preemptable packets, the delays of the not-preempted packets will be reduced. The basic idea of allowing applications to mark certain packets to express their "drop preference" and then having the network discard these packets if the network is congested has been circulating in the Internet community for years, and has been simulated in Reference []. The usual problem in such a scheme is defining what congestion means. In the Internet, with its simple service model, one usually equates congestion with the presence of a sizable queue. However, this is a network-centric definition that is not directly related to the quality of service desired by the various applications. In contrast, in our setting, we can make a very precise definition of congestion that is directly tied to the applications' service requirements: congestion is when some of the quantitative service commitments are in danger of being violated. The goal of admission control is to ensure that this situation arises extremely infrequently. Shenker, Clark, Zhang [Page 26] Internet Draft Integrated Service Architecture October 1993 The basic idea of preemptability can usefully be extended in two directions. First, for the purposes of invoking the preemptability options, one can stretch the definition of a quantitative service commitment to include implicit commitments such as compliance with the historical record of performance. That is, one could choose to drop packets to make sure that the network continued to provide service that was consistent with its past history, even if that past history was never explicitly committed to. Furthermore, one could also extend the definition of a quantitative service commitment to the utilization targets discussed above. Second, one can define a class of packets which are not subject to admission control. In the scenario described above where preemptable packets are dropped only when quantitative service commitments are in danger of being violated, the expectation is that preemptable packets will almost always be delivered and thus they must included in the traffic description used in admission control. However, we can extend preemptability to the extreme case of "expendable" packets (the term expendable is used to connote an extreme degree of preemptability), where the expectation is that many of these expendable packets will not be delivered. One can then exclude expendable packets from the traffic description used in admission control; i.e., the packets are not considered part of the flow from the perspective of admission control, since there is no commitment that they will be delivered. Such expendable packets could be dropped not only when quantitative service commitments are in danger of being violated, but also when implicit commitments and utilization targets, as described above, are in danger of being violated. The goal of these preemptable and expendable denial of service options (both at the packet and flow level of granularity) is to identify and take advantage of those flows that are willing to suffer some interruption of service (either through the loss of packets or the termination of the flow) in exchange for a lower cost. The preemptable flows and packets provide the network with a margin of error, or a "cushion", for absorbing rare statistical fluctuations in the load. This will allow the network to operate at a higher level of utilization without endangering the service commitments made to those flows who do not choose preemptable service. Similarly, expendable packets can be seen as "filler" for the network; they will be serviced only if they do not interfere with any service commitment but there is no expectation that their being dropped is a rare event. This will increase the level of utilization even further. We will not specify further how these denial of service, or preemptability, options are defined, but clearly there can be several levels of Shenker, Clark, Zhang [Page 27] Internet Draft Integrated Service Architecture October 1993 preemptability, so that an application's willingness to be disrupted can be measured on more than a binary scale. 6 Alternative Viewpoints In this section, we discuss several other viewpoints on the problem of providing integrated services. 6.1 Scheduling Algorithms vs. Service Models The motivating principle of this memo is that the service model is primary. However, one could contend that because we do not yet know the service needs of future applications, the most important goal is to design flexible and efficient packet scheduling implementations. Obviously both packet scheduling implementations and service models are tremendously important, but the debate here is over which one should guide the design of the Internet. There are three points to be made. First, the service model must be made explicit to application designers. Currently, there are a rather limited number of network-intensive applications; the network can, to a large extent, determine the service requirements of a packet by inspecting the port number. However, as the variety of network- intensive applications increases, and as the service requirements of these applications begin to depend on the user's personal demands (e.g., high and low priority mail, high and low quality video from the same codec, etc.), port numbers will no longer be sufficient to identify service requirements. Rather than having the network implicitly deliver the appropriate service, the applications will have to explicitly request the desired service. For this to happen, the service model must be made explicit (so that application designers know about it), and it obviously must remain relatively stable; the service model should not just be implicitly defined by the packet scheduling implementation. Thus, regardless of whether the packet scheduling algorithm is flexible or not, the service model must be made explicit and remain relatively stable. Second, there is a fundamental difference in the time-scale over which packet scheduling implementations and service models have impact. Once a router vendor with a substantial market presence adopts a new packet scheduling implementation, it will likely remain fixed for several years. So, in the short term, we need to ensure that such packet scheduling implementations embody enough flexibility to adapt if a new service model is adopted, or the current service model is extended, during the product's lifetime. However, router technology, and the embedded packet scheduling Shenker, Clark, Zhang [Page 28] Internet Draft Integrated Service Architecture October 1993 implementations, do evolve as new products are introduced, and so one cannot expect that packet scheduling implementations will remain fixed for many years. On the other hand, the time scale of service models is rather different. It typically takes much longer for a new service model to become adopted and utilized, because it must be embedded in user applications. However, once a service model does become adopted it is much harder to change, for precisely the same reason. Thus, we can say that while the set of packet scheduling implementations will likely freeze first, the service model freezes harder. For this reason we choose to focus on the service model. Third, the role of flexibility must be clarified. The services offered to individual flows by a packet scheduling algorithm must be part of a service model and, as we argued above, the service model does not change rapidly (except in experimental networks, where perhaps using flexible and efficient packet scheduling implementations is important); in particular, we expect service models to change much less rapidly than packet scheduling algorithms. Thus, for quality of service commitments to individual flows, flexibility is not of great importance. However, the link-sharing portion of the service model is not exercised by individual applications but rather by network managers through some network management interface. This portion of the service model can change much more rapidly, so flexibility is indeed important for link-sharing and other forms of resource sharing. The debate over the relative importance of service models and packet scheduling implementations reflects, at least in part, a deeper disagreement over the extent to which quality of service needs are met indirectly by link-sharing, which controls the aggregate bandwidth allocated to various collective entities, as opposed to being met directly by quality of service commitments to individual flows. Actually, the important distinction here is not between link-sharing and delay related services, but rather between those services which require explicit use of the service interface, and those that are delivered implicitly (i.e., based on information automatically included in the packet header such as port numbers). Network architectures designed around such implicit quality of service mechanisms do not require a well- defined service model; the network architecture we have advocated involves explicit quality of service mechanisms and therefore requires a stable service model. 6.2 Why Use Admission Control? Real-time service plays a central role in the proposed service model. We should note that there is another viewpoint on this issue, which has not yet been adequately articulated in the Shenker, Clark, Zhang [Page 29] Internet Draft Integrated Service Architecture October 1993 literature. It is conceivable that the combination of adaptive applications and sufficient overprovisioning of the network could render such delay bounds, with the associated need for admission control, unnecessary; applications could adapt to current network conditions, and the overprovisioning would ensure that the network was very rarely overloaded [Note 13] In this view, it would be sufficient to provide only the several classes of ASAP service without "any" real-time services. The first question is, can one indeed overprovision the network so that it is extremely rarely overloaded? It is true that the statistical demand in the phone network is well characterized, and overprovisioning has become a finely honed art. However, there are three crucial differences between the phone network and the Internet which lead us to the conclusion that the extreme variability of the offered load will require too great a degree of overprovisioning to make this approach practical. First, we do not expect the usage patterns on the Internet to be nearly so well characterized. In the phone network the usage patterns tend to revolve around human behavior, which changes rather slowly. However, in the Internet, the transfer of a few file repositories can create a dramatic and immediate shift in traffic patterns. Second, the variability in usage of an individual phone user is quite limited. In contrast, computer network usage can easily vary by three orders of magnitude, from 64kbps voice to 100mbps HDTV. Even if the law of large numbers does apply, the intrinsic variance of the individual distributions means that the resulting variance of the aggregate usage will be several orders of magnitude bigger than in the phone network. Third, regardless of price, there are natural intrinsic limits to the maximum bandwidth demand on the phone network: every person and FAX machine placing a call simultaneously. In contrast, there is no reason to expect that if bandwidth were sufficiently cheap there would be limits to the bandwidth consumption on the Internet (think of having video-on-demand everywhere). Thus, unless we use excessively high prices to artificially lower demand, we doubt we can overprovision the network so that it is extremely rarely overloaded. Given that overloads will occur if no admission control is used, the second question is: can applications adequately adapt to these overloaded conditions, or should we use admission control to prevent these overloads from occurring? Even if one assumes that adaptation is done instantaneously (so that there are no transient periods where the offset delays are incorrectly set), there is the basic question of whether the user population would be happier all _________________________ [Note 13] Of course, this viewpoint is predicated on the nonexistence of applications which have hard real-time requirements. Shenker, Clark, Zhang [Page 30] Internet Draft Integrated Service Architecture October 1993 sharing an overloaded network, or would they prefer having some users turned away. For typical elastic applications such as Telnet, it is most likely preferable to share the overloaded network. For typical real-time applications such as remote interactive video, we conjecture that it is preferable to turn some users away because the rapid increase in delays and packet drops as a function of load causes severe degradation of application performance even for adaptive applications. In short, the ability to adapt to worse conditions does not mean that appl A common counterargument to our line of reasoning is that users will be unhappy with any network that denies service with any significant frequency, and so we are merely trading off the unhappiness with overloading for the unhappiness caused by denial of service. While users may expect very low rates of denial for low-bandwidth applications like voice, there will not likely be the same expectation for extremely bandwidth intensive applications like HDTV. We expect that it will be rather easy, and fairly efficient (i.e., result in a reasonably high utilization level), to provision the network so that it can easily accept almost all phone calls, but will occasionally turn away much larger bandwidth requests. 6.3 Variations on the Service Model There are other approaches to defining real-time service. The real-time service advocated here provides a bound on the maximum delay of packets, provided that the application's traffic load conforms to some prearranged filter. One could provide not only a bound on the maximum delay but also a nontrivial bound (i.e., a bound other than the no-queueing bound) on the minimum delay. We did not include such nontrivial lower bounds on delay in our present service model because they serve only to reduce buffering at the receiver and we do not expect buffers to be a bottleneck; furthermore, if some applications do need additional buffering, this can easily be supplied at the edge of the network and need not be built into the basic core service model. A rather different form of service model is to offer statistical characterizations of performance. We explicitly reject such statistically characterized service offerings because they inherently require a statistical characterization of individual flows (or at least of the aggregate traffic), and we doubt that such characterizations will be available. Instead, we rely only on worst-case characterizations of the flows. Finally, one can define different link-sharing service models; in Shenker, Clark, Zhang [Page 31] Internet Draft Integrated Service Architecture October 1993 particular, as discussed in [], one can incorporate priorities between entities into the link-sharing service model (the model presented here does include priorities in a single entity's traffic, but not between entities). We do not include this feature for two reasons. First, a basic principle of this service model is that the quality of service requirements of individual applications should be addressed primarily through explicit service requests. Second, and much more importantly, the priority features will not produce dramatically different delay behaviors unless the traffic is very close to the bandwidth limits imposed by link-sharing. 7 Acknowledgments We would like to acknowledge that the thoughts discussed in this memo reflect the contributions of many others. In particular, the works of Parekh and Gallager [29,18], Ferrari et al. [6,,7,19], Jacobson and Floyd [,11,], Golestani [15,9], Guerin et al. [,20], Kurose et al. [,,33,,], Lazar et al. [,,22,], and Kalmanek et al. [13] have been critical in shaping our thinking on this matter. Discussions with our ISIP collaborators, the End-to-End Services Research Group, the authors of the above works, and many of our other colleagues have also been instrumental in clarifying our thoughts. In particular, Abhay Parekh has taught us much about the delay bound results in [29,18]. Also, Sally Floyd and Van Jacobson have rightly insisted that packet scheduling algorithms must deal with packet dropping and hierarchical link-sharing; we wish to acknowledge that much of our thinking on the hierarchical nature of link-sharing was stimulated by, and borrows heavily from, their work. REFERENCES [1] S. Casner. "private communication", 1992. [2] D. Clark and V. Jacobson. "Flexible and Efficient Resource management for Datagram Networks", unpublished draft, 1991. [3] D. Clark, S. Shenker, and L. Zhang. "Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism", in Proceedings of SIGCOMM '92, pp 14-26, 1992. [4] R. Chipalkatti, J. Kurose, and D. Towsley. "Scheduling Policies for Real-Time and Non-Real-Time Traffic in a Statistical Multiplexer", in Proceedings of GlobeCom '89, pp 774-783, 1989. [5] R. Cocchi, D. Estrin, S. Shenker, and L. Zhang. "A Study of Priority Pricing in Multiple Service Class Networks", in Proceedings of SIGCOMM '91, pp 123-130, 1991. Shenker, Clark, Zhang [Page 32] Internet Draft Integrated Service Architecture October 1993 [6] R. Cocchi, D. Estrin, S. Shenker, and L. Zhang. "Pricing in Computer Networks: Motivation, Formulation, and Example", preprint, 1992. [7] A.~Demers, S.~Keshav, and S.~Shenker. "Analysis and Simulation of a Fair Queueing Algorithm", In Journal of Internetworking: Research and Experience, 1, pp. 3-26, 1990. Also in Proc. ACM SIGCOMM '89, pp 3-12. [8] J. DeTreville and D. Sincoskie. "A Distributed Experimental Communications System", In IEEE JSAC, Vol. 1, No. 6, pp 1070-1075, December 1983. [9] D. Ferrari. "Client Requirements for Real-Time Communication Services", In IEEE Communications Magazine, 28(11), November 1990. [10] D. Ferrari. "Distributed Delay Jitter Control in Packet-Switching Internetworks", In Journal of Internetworking: Research and Experience, 4, pp. 1-20, 1993. [11] D. Ferrari, A. Banerjea, and H. Zhang "Network Support for Multimedia", preprint, 1992. [12] D. Ferrari and D. Verma. "A Scheme for Real-Time Channel Establishment in Wide-Area Networks", In IEEE JSAC, Vol. 8, No. 3, pp 368-379, April 1990. [13] S. Floyd. "Link-sharing and Resource Management Models for Packet Networks", preprint, 1993. [14] S. J. Golestani. "A Stop and Go Queueing Framework for Congestion Management", In Proceedings of SIGCOMM '90, pp 8-18, 1990. [15] S. J. Golestani. "Duration-Limited Statistical Multiplexing of Delay Sensitive Traffic in Packet Networks", In Proceedings of INFOCOM '91, 1991. [16] R. Gu'erin and L. G"un. "A Unified Approach to Bandwidth Allocation and Access Control in Fast Packet-Switched Networks", In Proceedings of INFOCOM '92. [17] R. Gu'erin, H. Ahmadi, and M. Naghshineh. "Equivalent Capacity and Its Application to Bandwidth Allocation in High-Speed Networks", In IEEE JSAC, Vol. 9, No. 9, pp 968-981, September 1991. [18] J. Kurose. "Open Issues and Challenges in Providing Quality of Service Guarantees in High-Speed Networks", In Computer Communication Review, 23(1), pp 6-15, 1993. Shenker, Clark, Zhang [Page 33] Internet Draft Integrated Service Architecture October 1993 [19] J. Hyman and A. Lazar. "MARS: The Magnet II Real-Time Scheduling Algorithm", In Proceedings of SIGCOMM '91, pp 285-293, 1991. [20] J. Hyman, A. Lazar, and G. Pacifici. "Real-Time Scheduling with Quality of Service Constraints", In IEEE JSAC, Vol. 9, No. 9, pp 1052-1063, September 1991. [21] J. Hyman, A. Lazar, and G. Pacifici. "Joint Scheduling and Admission Control for ATS-based Switching Nodes", In Proceedings of SIGCOMM '92, 1992. [22] J. Hyman, A. Lazar, and G. Pacifici. "A Separation Principle Between Scheduling and Admission Control for Broadband Switching", In IEEE JSAC, Vol. 11, No. 4, pp 605-616, May 1993. [23] V. Jacobson and S. Floyd "private communication", 1991. [24] V. Jacobson "private communication", 1991. [25] S. Jamin, S. Shenker, L. Zhang, and D. Clark. "An Admission Control Algorithm for Predictive Real-Time Service", In Proceedings of the Third International Workshop on Networking and Operating System Support for Digital Audio and Video, 1992. [26] C. Kalmanek, H. Kanakia, and S. Keshav. "Rate Controlled Servers for Very High-Speed Networks", In Proceedings of GlobeCom '90, pp 300.3.1-300.3.9, 1990. [27] R. Nagarajan and J. Kurose. "On Defining, Computing, and Guaranteeing Quality-of-Service in High-Speed Networks", In Proceedings of INFOCOM '92, 1992. [28] A.~Parekh and R. Gallager. "A Generalized Processor Sharing Approach to Flow Control- The Single Node Case", In Technical Report LIDS-TR-2040, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, 1991. [29] A.~Parekh. "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks", In Technical Report LIDS- TR-2089, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, 1992. [30] C. Partridge, "A Proposed Flow Specification" RFC-1363, July 1992. [31] H. Schulzrinne "private communication", 1992. [32] H. Schulzrinne, J. Kurose, and D. Towsley. "Congestion Control for Real-Time Traffic", In Proceedings of INFOCOM '90. Shenker, Clark, Zhang [Page 34] Internet Draft Integrated Service Architecture October 1993 [33] S. Shenker "Service Models and Pricing Policies for an Integrated Services Internet", to appear in Proceedings of "Public Access to the Internet", Harvard University, 1993. [34] S. Shenker, D. Clark, and L. Zhang. "A Scheduling Service Model and a Scheduling Architecture for an Integrated Services Packet Network" preprint, 1993. [35] D. Verma, H. Zhang, and D. Ferrari. "Delay Jitter Control for Real-Time Communication in a Packet Switching Network", In Proceedings of TriCom '91, pp 35-43, 1991. [36] C. Weinstein and J. Forgie. "Experience with Speech Communication in Packet Networks", In IEEE JSAC, Vol. 1, No. 6, pp 963-980, December 1983. [37] D. Yates, J. Kurose, D. Towsley, and M. Hluchyj. "On Per-Session End-to-End Delay Distribution and the Call Admission Problem for Real Time Applications with QOS Requirements", In Proceedings of SIGCOMM '93, to appear. [38] L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala, "RSVP: A New Resource ReSerVation Protocol", Accepted for publication in IEEE Network, 1993. A. On Standardizing a Service Model Let us assume, for the sake of argument, that the Internet community agrees to adopt a service model similar in spirit to the one proposed here. There is then the question of how one "standardizes" the service model. There are two approaches. First, one could identify a single packet forwarding algorithm which supports this service model and then require that all routers use this algorithm. This entails standardizing the detailed packet scheduling mechanisms in the routers. It is not clear that all router technologies will be able to implement this particular packet scheduling mechanism, and so this approach may limit the range of technologies that can be employed in the Internet. One expects, in fact for the sake of progress one hopes, that the future Internet will have a diverse set of underlying technologies, and so requiring uniformity of the packet forwarding algorithm is probably not realistic nor desirable. The second approach involves adopting the service model without specifying the underlying mechanism. This path, while not nearly as straightforward (in fact, it poses a special challenge to the Internet's standardization procedures), is far more flexible. In this second approach there are several different conceptual issues which must be dealt with: (1) what services will be Shenker, Clark, Zhang [Page 35] Internet Draft Integrated Service Architecture October 1993 offered, (2) how are those services requested by the application, and (3) how are those services provided by the network. In this section we briefly address these three issues. A.1 Defining the Services There are two separate components to defining the set of services offered by the network: the service model and the service specification. Service Model This is the basic set of services offered by the network and, as such, is the central expression of the network architecture. As we have argued previously, the service model should be based on fundamental application requirements. We have proposed a core service model in this memo. For individual flows it provides for two kinds of real-time service, guaranteed service and predictive service, along with multiple levels of elastic service. The service model also provides for hierarchical link- sharing services between collective entities. Service Specification This is the detailed parameterization of the service model. This specification details how the service delivered to flows is characterized (e.g., delay bounds, etc.). In addition, the service specification details both how flows characterize themselves to the network (e.g., token bucket, leaky bucket, peak rate, etc.), and how these characterizations are enforced the network (e.g., by dropping or delaying packets, at entry points or at every router, etc.). While the service model is derived from rather general principles, the service specification involves making a number of detailed (and perhaps arbitrary) engineering choices. A.2 Obtaining the Services There are three kinds of services: link-sharing, elastic, and real- time. The link-sharing services will presumably be controlled through a network management interface. Since this network management interface will not typically be invoked by widely-used applications, there are few compatibility constraints. Thus, this interface can gradually evolve and so we need not be concerned with making its definition precise now. Since providing elastic service requires no preallocation of resources, we presume that applications Shenker, Clark, Zhang [Page 36] Internet Draft Integrated Service Architecture October 1993 utilizing elastic service will not need to pass through admission control. These elastic service desires (i.e., which level of ASAP service, and the preemptability of the packets) will probably be specified by the application in the interface to the transport protocol, and this will in turn be communicated to the network through some indication in the individual packet headers. We assume that this will be addressed in some other standardization venue, and we will not address it further here. In contrast, providing the real-time services does require preallocation of network resources. Applications desiring real-time service will have to first explicitly request that service, and this request involves reserving network resources. The reservation procedure has two steps; first the application will invoke some operating system interface to request the reservation, and then some "set-up" or "reservation" protocol will forward that request to the network and return an answer. The application logically sees a request-response semantics through some operating system interface; the routers interact not with the application but with the reservation protocol and that can have a different interface. The set-up protocol has its own "service model" of the various configurations of reserved state it can provide; these were deemed "reservation styles" in [10] (we are not advocating the particular reservation styles in [10] but are merely citing them as examples of nontrivial relationships between flows and reserved resources). As an example of this we note that so far in our exploration of the service model, we have discussed only the service given to actual flows (that is, flows whose packets are forwarded by the network). However, one can reserve resources for potential flows as well; potential flows are those whose packets are not currently being forwarded, but for whom resources have been reserved. Thus, in defining how applications obtain real-time services, we must deal with the reservation model of the set-up protocol and not just the service model of the network itself. We also must describe what information is passed between the applications and the network, and then must provide a detailed description of the interface invoked by applications. More specifically, the three conceptual pieces are: Reservation Model The reservation model describes what configurations of resources can be reserved. The reservation model must not only address the service model available to individual flows, but must also incorporate more general configurations of reserved resources. Shenker, Clark, Zhang [Page 37] Internet Draft Integrated Service Architecture October 1993 Negotiation Model The negotiation model describes, at an architectural level, (1) what parameters the application hands to the operating system interface, and (2) what parameters the application gets back from that interface. The negotiation model will depend on, and may therefore dictate, which end (source, receiver) of the application is submitting the requests. The negotiation model will also have implications for the set of queries and responses implemented in the admission control algorithm. Reservation Interface This is a detailed parameterization (essentially the API) of the negotiation model. This reservation interface will be the artifact that is invoked by applications. It should be designed to be properly extensible, so that new services can be added, but it will inevitably be subject to compatibility constraints and therefore the previously defined components will be largely immutable. A.3 Providing the Services The previous two sections specify the range of services available, and how an application can obtain them. If there were a single network provider, then we would just require that the network support the interface to the set-up protocol and deliver the desired service. However, the Internet is, and will likely continue to be, a very heterogeneous and administratively decentralized institution. The service delivered to a flow is a concatenation of the service provided by the various routers along its path, and these routers need not implement the same packet forwarding algorithms. Thus, we need to directly address how we can be assured that such a network, with local operators making decisions about which routers to install, will indeed support the service model. As mentioned previously, one approach is to insist on a single router mechanism. The approach we advocate is, instead, to provide a functional requirement on routers rather than a definition of the detailed mechanism. Router Interoperability Requirements This specifies a set of criteria that a router has to conform to. There are two categories of criteria. First, Shenker, Clark, Zhang [Page 38] Internet Draft Integrated Service Architecture October 1993 the routers must implement the interface used by the set-up protocol, and the admission control algorithm must support the appropriate set of queries. Incorporated within this is something functionally equivalent to what is described in RFC 1363 [3], which describes the set of parameters handed to routers along the path of a flow. Second, the service delivered by the router must conform to certain standards; these standards are designed so that the service delivered by a heterogeneous set of conforming routers will obey the service model. For guaranteed service, one might require that routers must approximate the WFQ "fluid model", as defined in []. One can express the accuracy to which a router supports the fluid model with an error term which can be carried in the reservation interface as it is passed between routers and added up to compute the resulting end-to-end delay bounds. We should note that this is just one example; there are other alternatives for specifying how to deliver guaranteed service. For predictive service, the issue is much more difficult. Here the performance depends crucially on the admission control algorithm [Note 14], and it is difficult to accurately characterize a measurement-based admission control algorithm. We propose that the performance of such algorithms be characterized by their performance on various test suites. These test suites will reveal not only the degree to which the delay bounds are met, but also the level of network utilization obtained (which depends on the behavior of the admission control algorithm). How one defines and evaluates such test suites is an unexplored yet crucial issue. _________________________ [Note 14] The guaranteed service depends on admission control as well, but for guaranteed service there is a clear correctness condition for admission control. There is no such clear correctness condition for predictive admission control. Shenker, Clark, Zhang [Page 39]